package com.linyaonan.leetcode.easy._1175;

import java.math.BigInteger;

/**
 * 请你帮忙给从 1 到 n 的数设计排列方案，使得所有的「质数」都应该被放在「质数索引」（索引从 1 开始）上；你需要返回可能的方案总数。
 * <p>
 * 让我们一起来回顾一下「质数」：质数一定是大于 1 的，并且不能用两个小于它的正整数的乘积来表示。
 * <p>
 * 由于答案可能会很大，所以请你返回答案 模 mod 10^9 + 7 之后的结果即可。
 * <p>
 *  
 * <p>
 * 示例 1：
 * <p>
 * 输入：n = 5
 * 输出：12
 * 解释：举个例子，[1,2,5,4,3] 是一个有效的排列，但 [5,2,3,4,1] 不是，因为在第二种情况里质数 5 被错误地放在索引为 1 的位置上。
 * 示例 2：
 * <p>
 * 输入：n = 100
 * 输出：682289015
 *  
 * <p>
 * 提示：
 * <p>
 * 1 <= n <= 100
 *
 * @author: Lin
 * @date: 2020/1/11
 */
public class PrimeArrangements {

    public int numPrimeArrangements(int n) {
        if (n == 1) {
            return 1;
        }
        if (n == 2 || n == 3) {
            return n - 1;
        }
        int[] prime = new int[]{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97};
        int count = 0;
        for (int i = 0; i < prime.length; i++) {
            if (n < prime[i]) {
                break;
            } else {
                count++;
            }
        }
        BigInteger p = doFactorial(count);
        BigInteger t = doFactorial(n - count);
        BigInteger z = p.multiply(t);
        BigInteger mod = z.mod(BigInteger.valueOf(1000000007L));
        return mod.intValue();
    }

    private BigInteger doFactorial(int n) {
        BigInteger result = BigInteger.valueOf(1L);
        for (long i = 1L; i <= n; i++) {
            result = result.multiply(BigInteger.valueOf(i)).mod(BigInteger.valueOf(1000000007L));
        }
        return result;
    }

}
